/**
https://leetcode.cn/problems/open-the-lock/description/
752. 打开转盘锁
 Medium, 方钊堉 2024.12.07
 BFS
 */

class Solution {
public:
    int openLock(vector<string>& deadends, string target) {
        // 将死锁字符串存入哈希集合
        unordered_set<string> deadSet(deadends.begin(), deadends.end());

        // 初始化队列和访问集合
        queue<string> q;
        unordered_set<string> visited;

        // 从起点 "0000" 开始广度优先搜索
        q.push("0000");
        visited.insert("0000");

        int steps = 0; // 记录步数

        while (!q.empty()) {
            int size = q.size(); // 当前层的节点数量
            for (int i = 0; i < size; ++i) {
                string current = q.front();
                q.pop();

                // 如果当前状态是死锁，跳过
                if (deadSet.count(current)) {
                    continue;
                }

                // 如果当前状态是目标状态，返回步数
                if (current == target) {
                    return steps;
                }

                // 尝试转动每一位，生成新的状态
                for (int j = 0; j < 4; ++j) {
                    string up = turnUp(current, j);
                    if (!visited.count(up)) {
                        q.push(up);
                        visited.insert(up);
                    }

                    string down = turnDown(current, j);
                    if (!visited.count(down)) {
                        q.push(down);
                        visited.insert(down);
                    }
                }
            }
            ++steps; // 每处理完一层，步数加1
        }

        // 如果无法到达目标状态，返回 -1
        return -1;
    }

private:
    // 将第 j 位向上转一位
    string turnUp(string s, int j) {
        if (s[j] == '9') {
            s[j] = '0';
        } else {
            s[j] += 1;
        }
        return s;
    }

    // 将第 j 位向下转一位
    string turnDown(string s, int j) {
        if (s[j] == '0') {
            s[j] = '9';
        } else {
            s[j] -= 1;
        }
        return s;
    }
};